package day_2022_4_to_7.nowcoder;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 按之字形顺序打印二叉树
 *
 * @author haomin
 * @date 2022/05/13 16:38
 **/
public class PrintBinTreeByZhi_34 {

    // 方法一：
    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        if (pRoot == null) {
            return new ArrayList<>();
        }
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(pRoot);

        // 1 表示正序 ，2 表示逆序
        // 先默认flag为2 ，进入while时 保证第一次是正序
        int flag = 2;
        while (!queue.isEmpty()) {
            ArrayList<Integer> list = new ArrayList<>();
            ArrayList<Integer> reList = new ArrayList<>();

            int size = queue.size();
            flag = flag == 2 ? 1 : 2;
            for (int i = 0; i < size; i++) {
                TreeNode cur = queue.poll();
                if (flag == 1) {
                    list.add(cur.val);
                } else {
                    reList.add(cur.val);
                }

                if (cur.left != null) queue.offer(cur.left);
                if (cur.right != null) queue.offer(cur.right);
            }
            // 将该层数逆置存入list
            for (int i = reList.size() - 1; i >= 0; i--) {
                list.add(reList.get(i));
            }
            result.add(list);
        }
        return result;
    }

    // 方法二：
    public ArrayList<ArrayList<Integer>> Print2(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        if (pRoot == null) {
            return result;
        }
        Stack<TreeNode> st = new Stack<>();
        Queue<TreeNode> q = new LinkedList<>(); //临时区域

        st.push(pRoot);
        int dir = 1;
        //1：代表left->right式入栈. 2: 代表right->left式入栈
        ArrayList<Integer> list = new ArrayList<>();//保存一层结果的临时变量

        while (!st.empty()) {
            int size = st.size();
            //清空本层所有节点，将下层节点按照要求入栈，栈具有天然的逆序的能力
            for (int i = 0; i < size; i++) {
                TreeNode curr = st.pop();
                list.add(curr.val);
                TreeNode first = (dir == 1) ? curr.left : curr.right;
                TreeNode second = (dir == 1) ? curr.right : curr.left;
                if (first != null) q.offer(first);
                if (second != null) q.offer(second);
            }
            //本层遍历完毕，入结果集
            result.add(new ArrayList(list));
            //一定要注意浅拷贝问题
            list.clear();
            //将所有节点入栈，进行逆序
            while (!q.isEmpty()) {
                st.push(q.poll());
            }
            dir = (dir == 1) ? 2 : 1;
        }
        return result;
    }
}